#include "config.h"
#include "ecm.h"

typedef struct _treenode {
	int	balance;		/* height (left) - height (right) */
	struct _treenode *left, *right;	/* left & right subtree */
	void	*key;			/* key for this node */
	void	*value;			/* value stored at this node */
} ecm_tree_node_t;

typedef struct {
	ecm_tree_node_t	      *root;
	ecm_comparedatafunc_t key_compare;
	ecm_dtornotify_t      key_destroy_func;
	ecm_dtornotify_t      value_destroy_func;
	void     *key_compare_data;
} tree_t;

static ecm_tree_node_t *ecm_tree_node_new(void *key, void *value);
static void ecm_tree_node_destroy(ecm_tree_node_t *node,
				  ecm_dtornotify_t key_destroy_func,
				  ecm_dtornotify_t value_destroy_func);
static ecm_tree_node_t *ecm_tree_node_insert(tree_t * tree,
					     ecm_tree_node_t *node,
					     void *key,
					     void *value,
					     ECMBOOL replace,
					     ECMBOOL * inserted);
static ecm_tree_node_t *ecm_tree_node_remove(tree_t * tree,
					     ecm_tree_node_t *node,
					     const void *key, ECMBOOL notify);
static ecm_tree_node_t *ecm_tree_node_balance(ecm_tree_node_t *node);
static ecm_tree_node_t *ecm_tree_node_remove_leftmost(ecm_tree_node_t *node,
						      ecm_tree_node_t **leftmost);
static ecm_tree_node_t *ecm_tree_node_restore_left_balance(ecm_tree_node_t *node,
							   int old_balance);
static ecm_tree_node_t *ecm_tree_node_restore_right_balance(ecm_tree_node_t *node,
							    int old_balance);
static ecm_tree_node_t *ecm_tree_node_lookup(ecm_tree_node_t *node,
					     ecm_comparedatafunc_t compare,
					     void *comp_data,
					     const void *key);
static int ecm_tree_node_count(ecm_tree_node_t *node);
static int ecm_tree_node_pre_order(ecm_tree_node_t *node,
				   ecm_traversefunc_t traverse_func,
				   void *data);
static int ecm_tree_node_in_order(ecm_tree_node_t *node,
				  ecm_traversefunc_t traverse_func,
				  void *data);
static int ecm_tree_node_post_order(ecm_tree_node_t *node,
				    ecm_traversefunc_t traverse_func,
				    void *data);
static void *ecm_tree_node_search(ecm_tree_node_t *node,
				  ecm_comparefunc_t search_func,
				  const void *data);
static int ecm_tree_node_height(ecm_tree_node_t *node);
static ecm_tree_node_t *ecm_tree_node_rotate_left(ecm_tree_node_t *node);
static ecm_tree_node_t *ecm_tree_node_rotate_right(ecm_tree_node_t *node);

static ecm_mchunk_t *node_mem_chunk = NULL; 
static ecm_tree_node_t *node_free_list = NULL;

static ecm_tree_node_t *
ecm_tree_node_new(void *key, void *value)
{
	ecm_tree_node_t *node;

	if (node_free_list) {
		node = node_free_list;
		node_free_list = node->right;
	} else {
		if (!node_mem_chunk)
			node_mem_chunk = 
				ecm_mchunk_new("ecm_tree_node_t mem chunk",
						  sizeof(ecm_tree_node_t), 
						  1024,
						  ECM_MCHUNK_ALLOCONLY); 

		node = (ecm_tree_node_t *)ecm_mchunk_alloc(node_mem_chunk);
	}

	node->balance = 0;
	node->left = NULL;
	node->right = NULL;
	node->key = key;
	node->value = value;

	return node;
}

static void
ecm_tree_node_destroy(ecm_tree_node_t *node,
		      ecm_dtornotify_t key_destroy_func,
		      ecm_dtornotify_t value_destroy_func) 
{
	if (node) {
		ecm_tree_node_destroy(node->right,
				      key_destroy_func, value_destroy_func);
		ecm_tree_node_destroy(node->left,
				      key_destroy_func, value_destroy_func);

		if (key_destroy_func)
			key_destroy_func(node->key);
		if (value_destroy_func)
			value_destroy_func(node->value);

		node->right = node_free_list;
		node_free_list = node;
	}
}

/**
 * ecm_tree_new:
 * @key_compare_func: the function used to order the nodes in the #tree_t.
 *   It should return values similar to the standard strcmp() function -
 *   0 if the two arguments are equal, a negative value if the first argument 
 *   comes before the second, or a positive value if the first argument comes 
 *   after the second.
 * 
 * Creates a new #tree_t.
 * 
 * Return value: a new #tree_t.
 **/
ecm_tree_t
ecm_tree_new(ecm_comparefunc_t key_compare_func)
{
	ECM_RETURN_VAL_IF(key_compare_func == NULL, NULL);

	return ecm_tree_new_full((ecm_comparedatafunc_t)key_compare_func, 
				 NULL, NULL, NULL);
}

/**
 * ecm_tree_new_with_data:
 * @key_compare_func: qsort()-style comparison function.
 * @key_compare_data: data to pass to comparison function.
 * 
 * Creates a new #tree_t with a comparison function that accepts user data.
 * See ecm_tree_new() for more details.
 * 
 * Return value: a new #tree_t.
 **/
ecm_tree_t
ecm_tree_new_with_data(ecm_comparedatafunc_t key_compare_func,
		       void *key_compare_data)
{
	ECM_RETURN_VAL_IF(key_compare_func == NULL, NULL);

	return ecm_tree_new_full(key_compare_func, key_compare_data,
				 NULL, NULL);
}

/**
 * ecm_tree_new_full:
 * @key_compare_func: qsort()-style comparison function.
 * @key_compare_data: data to pass to comparison function.
 * @key_destroy_func: a function to free the memory allocated for the key 
 *   used when removing the entry from the #tree_t or %NULL if you don't
 *   want to supply such a function.
 * @value_destroy_func: a function to free the memory allocated for the 
 *   value used when removing the entry from the #tree_t or %NULL if you 
 *   don't want to supply such a function.
 * 
 * Creates a new #tree_t like ecm_tree_new() and allows to specify functions 
 * to free the memory allocated for the key and value that get called when 
 * removing the entry from the #tree_t.
 * 
 * Return value: a new #tree_t.
 **/
ecm_tree_t
ecm_tree_new_full(ecm_comparedatafunc_t key_compare_func,
		  void *key_compare_data,
		  ecm_dtornotify_t key_destroy_func,
		  ecm_dtornotify_t value_destroy_func)
{
	tree_t	*tree;

	ECM_RETURN_VAL_IF(key_compare_func == NULL, NULL);

	tree = malloc(sizeof(tree_t));
	tree->root = NULL;
	tree->key_compare = key_compare_func;
	tree->key_destroy_func = key_destroy_func;
	tree->value_destroy_func = value_destroy_func;
	tree->key_compare_data = key_compare_data;

	return (ecm_tree_t)tree;
}

/**
 * ecm_tree_destroy:
 * @tree: a #ecm_tree_t.
 * 
 * Destroys the #ecm_tree_t. If keys and/or values are dynamically allocated, you 
 * should either free them first or create the #ecm_tree_t using ecm_tree_new_full().
 * In the latter case the destroy functions you supplied will be called on 
 * all keys and values before destroying the #ecm_tree_t.
 **/
void
ecm_tree_destroy(ecm_tree_t ecm_tree)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_IF(tree == NULL);

	ecm_tree_node_destroy(tree->root,
			      tree->key_destroy_func,
			      tree->value_destroy_func);
	free(tree);
}

/**
 * ecm_tree_insert:
 * @tree: a #ecm_tree_t
 * @key: the key to insert.
 * @value: the value corresponding to the key.
 * 
 * Inserts a key/value pair into a #ecm_tree_t. If the given key already exists 
 * in the #ecm_tree_t its corresponding value is set to the new value. If you 
 * supplied a value_destroy_func when creating the #ecm_tree_t, the old value is 
 * freed using that function. If you supplied a @key_destroy_func when 
 * creating the #ecm_tree_t, the passed key is freed using that function.
 *
 * The tree is automatically 'balanced' as new key/value pairs are added,
 * so that the distance from the root to every leaf is as small as possible.
 **/
void
ecm_tree_insert(ecm_tree_t ecm_tree, void *key, void *value)
{
	tree_t	*tree = (tree_t *)ecm_tree;
	ECMBOOL	inserted;

	ECM_RETURN_IF(tree == NULL);

	inserted = ECM_FALSE;
	tree->root = ecm_tree_node_insert(tree, tree->root, key, 
					  value, ECM_FALSE, &inserted);
}

/**
 * ecm_tree_replace:
 * @tree: a #ecm_tree_t.
 * @key: the key to insert.
 * @value: the value corresponding to the key.
 * 
 * Inserts a new key and value into a #ecm_tree_t similar to ecm_tree_insert(). 
 * The difference is that if the key already exists in the #ecm_tree_t, it gets 
 * replaced by the new key. If you supplied a @value_destroy_func when 
 * creating the #ecm_tree_t, the old value is freed using that function. If you 
 * supplied a @key_destroy_func when creating the #ecm_tree_t, the old key is 
 * freed using that function. 
 *
 * The tree is automatically 'balanced' as new key/value pairs are added,
 * so that the distance from the root to every leaf is as small as possible.
 **/
void
ecm_tree_replace(ecm_tree_t ecm_tree, void *key, void *value)
{
	tree_t	*tree = (tree_t *)ecm_tree;
	ECMBOOL inserted;

	ECM_RETURN_IF(tree == NULL);

	inserted = ECM_FALSE;
	tree->root = ecm_tree_node_insert(tree, tree->root, key, 
					  value, ECM_TRUE, &inserted);
}

/**
 * ecm_tree_remove:
 * @tree: a #ecm_tree_t.
 * @key: the key to remove.
 * 
 * Removes a key/value pair from a #ecm_tree_t.
 *
 * If the #ecm_tree_t was created using ecm_tree_new_full(), the key and value 
 * are freed using the supplied destroy functions, otherwise you have to 
 * make sure that any dynamically allocated values are freed yourself.
 **/
void 
ecm_tree_remove(ecm_tree_t ecm_tree, const void *key)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_IF(tree == NULL);

	tree->root = ecm_tree_node_remove(tree, tree->root, key, ECM_TRUE);
}

/**
 * ecm_tree_steal:
 * @tree: a #ecm_tree_t.
 * @key: the key to remove.
 * 
 * Removes a key and its associated value from a #ecm_tree_t without calling 
 * the key and value destroy functions.
 **/
void 
ecm_tree_steal(ecm_tree_t ecm_tree, const void *key)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_IF(tree == NULL);

	tree->root = ecm_tree_node_remove(tree, tree->root, key, ECM_FALSE);
}

/**
 * ecm_tree_lookup:
 * @tree: a #ecm_tree_t.
 * @key: the key to look up.
 * 
 * Gets the value corresponding to the given key. Since a #ecm_tree_t is 
 * automatically balanced as key/value pairs are added, key lookup is very 
 * fast.
 *
 * Return value: the value corresponding to the key.
 **/
void *
ecm_tree_lookup(ecm_tree_t ecm_tree, const void *key)
{
	tree_t	*tree = (tree_t *)ecm_tree;
	ecm_tree_node_t *node;

	ECM_RETURN_VAL_IF(tree == NULL, NULL);

	node = ecm_tree_node_lookup(tree->root,
				    tree->key_compare,
				    tree->key_compare_data, key);

	return node ? node->value : NULL;
}

/**
 * ecm_tree_lookup_extended:
 * @tree: a #ecm_tree_t.
 * @lookup_key: the key to look up.
 * @orig_key: returns the original key.
 * @value: returns the value associated with the key.
 * 
 * Looks up a key in the #ecm_tree_t, returning the original key and the
 * associated value and a #ECMBOOL which is %ECM_TRUE if the key was found. This 
 * is useful if you need to free the memory allocated for the original key, 
 * for example before calling ecm_tree_remove().
 * 
 * Return value: %ECM_TRUE if the key was found in the #ecm_tree_t.
 **/
ECMBOOL
ecm_tree_lookup_extended(ecm_tree_t ecm_tree,
			 const void *lookup_key,
			 void **orig_key, void **value)
{
	tree_t	*tree = (tree_t *)ecm_tree;
	ecm_tree_node_t *node;

	ECM_RETURN_VAL_IF(tree == NULL, ECM_FALSE);

	node = ecm_tree_node_lookup(tree->root,
				    tree->key_compare,
				    tree->key_compare_data, lookup_key);

	if (node) {
		if (orig_key)
			*orig_key = node->key;
		if (value)
			*value = node->value;
		return ECM_TRUE;
	} else
		return ECM_FALSE;
}

/**
 * ecm_tree_foreach:
 * @tree: a #ecm_tree_t.
 * @func: the function to call for each node visited. If this function
 *   returns %ECM_TRUE, the traversal is stopped.
 * @user_data: user data to pass to the function.
 * 
 * Calls the given function for each of the key/value pairs in the #ecm_tree_t.
 * The function is passed the key and value of each pair, and the given
 * @data parameter. The tree is traversed in sorted order.
 *
 * The tree may not be modified while iterating over it (you can't 
 * add/remove items). To remove all items matching a predicate, you need 
 * to add each item to a list in your #ecm_traversefunc_t as you walk over 
 * the tree, then walk the list and remove each item.
 **/
void 
ecm_tree_foreach(ecm_tree_t ecm_tree, ecm_traversefunc_t func, void *user_data)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_IF(tree == NULL);

	if (!tree->root)
		return;

	ecm_tree_node_in_order(tree->root, func, user_data);
}

/**
 * ecm_tree_traverse:
 * @tree: a #ecm_tree_t.
 * @traverse_func: the function to call for each node visited. If this 
 *   function returns %ECM_TRUE, the traversal is stopped.
 * @traverse_type: the order in which nodes are visited, one of %G_IN_ORDER,
 *   %G_PRE_ORDER and %G_POST_ORDER.
 * @user_data: user data to pass to the function.
 * 
 * Calls the given function for each node in the #ecm_tree_t. 
 *
 * Deprecated: The order of a balanced tree is somewhat arbitrary. If you 
 * just want to visit all nodes in sorted order, use ecm_tree_foreach() 
 * instead. If you really need to visit nodes in a different order, consider
 * using an <link linkend="glib-N-ary-Trees">N-ary Tree</link>.
 **/
void
ecm_tree_traverse(ecm_tree_t ecm_tree, ecm_traversefunc_t traverse_func,
		  ecm_traversetype_t traverse_type, void *user_data)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_IF(tree == NULL);

	if (!tree->root)
		return;

	switch (traverse_type) {
	case ECM_PRE_ORDER:
		ecm_tree_node_pre_order(tree->root, traverse_func, user_data);
		break;

	case ECM_IN_ORDER:
		ecm_tree_node_in_order(tree->root, traverse_func, user_data);
		break;

	case ECM_POST_ORDER:
		ecm_tree_node_post_order(tree->root, traverse_func, user_data);
		break;
	case ECM_LEVEL_ORDER:
		break;
	}
}

/**
 * ecm_tree_search:
 * @tree: a #ecm_tree_t.
 * @search_func: a function used to search the #ecm_tree_t. 
 * @user_data: the data passed as the second argument to the @search_func 
 * function.
 * 
 * Searches a #ecm_tree_t using @search_func.
 *
 * The @search_func is called with a pointer to the key of a key/value pair in the tree,
 * and the passed in @user_data. If @search_func returns 0 for a key/value pair, then
 * ecm_tree_search_func() will return the value of that pair. If @search_func returns -1,
 * searching will proceed among the key/value pairs that have a smaller key; if @search_func
 * returns 1, searching will proceed among the key/value pairs that have a larger key.
 *
 * Return value: the value corresponding to the found key, or %NULL if the key 
 * was not found.
 **/
void *
ecm_tree_search(ecm_tree_t ecm_tree, ecm_comparefunc_t search_func, 
		const void *user_data)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_VAL_IF(tree == NULL, NULL);

	if (tree->root)
		return ecm_tree_node_search(tree->root, search_func, 
					    user_data);
	else
		return NULL;
}

/**
 * ecm_tree_height:
 * @tree: a #ecm_tree_t.
 * 
 * Gets the height of a #ecm_tree_t.
 *
 * If the #ecm_tree_t contains no nodes, the height is 0.
 * If the #ecm_tree_t contains only one root node the height is 1.
 * If the root node has children the height is 2, etc.
 * 
 * Return value: the height of the #ecm_tree_t.
 **/
int 
ecm_tree_height(ecm_tree_t ecm_tree)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_VAL_IF(tree == NULL, 0);

	if (tree->root)
		return ecm_tree_node_height(tree->root);
	else
		return 0;
}

/**
 * ecm_tree_nnodes:
 * @tree: a #ecm_tree_t.
 * 
 * Gets the number of nodes in a #ecm_tree_t.
 * 
 * Return value: the number of nodes in the #ecm_tree_t.
 **/
int 
ecm_tree_nnodes(ecm_tree_t ecm_tree)
{
	tree_t	*tree = (tree_t *)ecm_tree;

	ECM_RETURN_VAL_IF(tree == NULL, 0);

	if (tree->root)
		return ecm_tree_node_count(tree->root);
	else
		return 0;
}

static ecm_tree_node_t *
ecm_tree_node_insert(tree_t *tree, ecm_tree_node_t *node, void *key,
		     void *value, ECMBOOL replace, ECMBOOL *inserted)
{
	int old_balance;
	int cmp;

	if (!node) {
		*inserted = ECM_TRUE;
		return ecm_tree_node_new(key, value);
	}

	cmp = tree->key_compare(key, node->key, tree->key_compare_data);
	if (cmp == 0) {
		*inserted = ECM_FALSE;

		if (tree->value_destroy_func)
			tree->value_destroy_func(node->value);

		node->value = value;

		if (replace) {
			if (tree->key_destroy_func)
				tree->key_destroy_func(node->key);

			node->key = key;
		} else {
			/* free the passed key */
			if (tree->key_destroy_func)
				tree->key_destroy_func(key);
		}

		return node;
	}

	if (cmp < 0) {
		if (node->left) {
			old_balance = node->left->balance;
			node->left = ecm_tree_node_insert(tree,
							  node->left,
							  key, value,
							  replace, inserted);

			if ((old_balance != node->left->balance)
			    && node->left->balance)
				node->balance -= 1;
		} else {
			*inserted = ECM_TRUE;
			node->left = ecm_tree_node_new(key, value);
			node->balance -= 1;
		}
	} else if (cmp > 0) {
		if (node->right) {
			old_balance = node->right->balance;
			node->right = ecm_tree_node_insert(tree,
							   node->right,
							   key, value,
							   replace,
							   inserted);

			if ((old_balance != node->right->balance)
			    && node->right->balance)
				node->balance += 1;
		} else {
			*inserted = ECM_TRUE;
			node->right = ecm_tree_node_new(key, value);
			node->balance += 1;
		}
	}

	if (*inserted) {
		if ((node->balance < -1) || (node->balance > 1))
			node = ecm_tree_node_balance(node);
	}

	return node;
}

static ecm_tree_node_t *
ecm_tree_node_remove(tree_t *tree, ecm_tree_node_t *node,
		     const void *key, ECMBOOL notify)
{
	ecm_tree_node_t *new_root;
	int old_balance;
	int cmp;

	if (!node)
		return NULL;

	cmp = tree->key_compare(key, node->key, tree->key_compare_data);
	if (cmp == 0) {
		ecm_tree_node_t *garbage;

		garbage = node;

		if (!node->right) {
			node = node->left;
		} else {
			old_balance = node->right->balance;
			node->right =
				ecm_tree_node_remove_leftmost(node->right,
							      &new_root);
			new_root->left = node->left;
			new_root->right = node->right;
			new_root->balance = node->balance;
			node = ecm_tree_node_restore_right_balance(new_root,
								   old_balance);
		}

		if (notify) {
			if (tree->key_destroy_func)
				tree->key_destroy_func(garbage->key);
			if (tree->value_destroy_func)
				tree->value_destroy_func(garbage->value);
		}
		garbage->right = node_free_list;
		node_free_list = garbage;
	} else if (cmp < 0) {
		if (node->left) {
			old_balance = node->left->balance;
			node->left =
				ecm_tree_node_remove(tree, node->left, key,
						     notify);
			node =
				ecm_tree_node_restore_left_balance(node,
								   old_balance);
		}
	} else if (cmp > 0) {
		if (node->right) {
			old_balance = node->right->balance;
			node->right =
				ecm_tree_node_remove(tree, node->right, key,
						     notify);
			node =
				ecm_tree_node_restore_right_balance(node,
								    old_balance);
		}
	}

	return node;
}

static ecm_tree_node_t *
ecm_tree_node_balance(ecm_tree_node_t *node)
{
	if (node->balance < -1) {
		if (node->left->balance > 0)
			node->left = ecm_tree_node_rotate_left(node->left);
		node = ecm_tree_node_rotate_right(node);
	} else if (node->balance > 1) {
		if (node->right->balance < 0)
			node->right =
				ecm_tree_node_rotate_right(node->right);
		node = ecm_tree_node_rotate_left(node);
	}

	return node;
}

static ecm_tree_node_t *
ecm_tree_node_remove_leftmost(ecm_tree_node_t *node, 
			      ecm_tree_node_t **leftmost)
{
	int old_balance;

	if (!node->left) {
		*leftmost = node;
		return node->right;
	}

	old_balance = node->left->balance;
	node->left = ecm_tree_node_remove_leftmost(node->left, leftmost);
	return ecm_tree_node_restore_left_balance(node, old_balance);
}

static ecm_tree_node_t *
ecm_tree_node_restore_left_balance(ecm_tree_node_t *node, int old_balance)
{
	if (!node->left)
		node->balance += 1;
	else if ((node->left->balance != old_balance) &&
		 (node->left->balance == 0))
		node->balance += 1;

	if (node->balance > 1)
		return ecm_tree_node_balance(node);
	return node;
}

static ecm_tree_node_t *
ecm_tree_node_restore_right_balance(ecm_tree_node_t *node, int old_balance)
{
	if (!node->right)
		node->balance -= 1;
	else if ((node->right->balance != old_balance) &&
		 (node->right->balance == 0))
		node->balance -= 1;

	if (node->balance < -1)
		return ecm_tree_node_balance(node);
	return node;
}

static ecm_tree_node_t *
ecm_tree_node_lookup(ecm_tree_node_t *node, ecm_comparedatafunc_t compare,
		     void *compare_data, const void *key)
{
	int cmp;

	if (!node)
		return NULL;

	cmp = (*compare) (key, node->key, compare_data);
	if (cmp == 0)
		return node;

	if (cmp < 0) {
		if (node->left)
			return ecm_tree_node_lookup(node->left, compare,
						    compare_data, key);
	} else if (cmp > 0) {
		if (node->right)
			return ecm_tree_node_lookup(node->right, compare,
						    compare_data, key);
	}

	return NULL;
}

static int 
ecm_tree_node_count(ecm_tree_node_t *node)
{
	int count;

	count = 1;
	if (node->left)
		count += ecm_tree_node_count(node->left);
	if (node->right)
		count += ecm_tree_node_count(node->right);

	return count;
}

static int
ecm_tree_node_pre_order(ecm_tree_node_t *node,
			ecm_traversefunc_t traverse_func, void *data)
{
	if ((*traverse_func) (node->key, node->value, data))
		return ECM_TRUE;
	if (node->left) {
		if (ecm_tree_node_pre_order(node->left, traverse_func, data))
			return ECM_TRUE;
	}
	if (node->right) {
		if (ecm_tree_node_pre_order
		    (node->right, traverse_func, data))
			return ECM_TRUE;
	}

	return ECM_FALSE;
}

static int
ecm_tree_node_in_order(ecm_tree_node_t *node,
		       ecm_traversefunc_t traverse_func, void *data)
{
	if (node->left) {
		if (ecm_tree_node_in_order(node->left, traverse_func, data))
			return ECM_TRUE;
	}
	if ((*traverse_func) (node->key, node->value, data))
		return ECM_TRUE;
	if (node->right) {
		if (ecm_tree_node_in_order(node->right, traverse_func, data))
			return ECM_TRUE;
	}

	return ECM_FALSE;
}

static int
ecm_tree_node_post_order(ecm_tree_node_t *node,
			 ecm_traversefunc_t traverse_func, void *data)
{
	if (node->left) {
		if (ecm_tree_node_post_order
		    (node->left, traverse_func, data))
			return ECM_TRUE;
	}
	if (node->right) {
		if (ecm_tree_node_post_order
		    (node->right, traverse_func, data))
			return ECM_TRUE;
	}
	if ((*traverse_func) (node->key, node->value, data))
		return ECM_TRUE;

	return ECM_FALSE;
}

static void *
ecm_tree_node_search(ecm_tree_node_t *node,
		     ecm_comparefunc_t search_func, const void *data)
{
	int dir;

	if (!node)
		return NULL;

	do {
		dir = (*search_func) (node->key, data);
		if (dir == 0)
			return node->value;

		if (dir < 0)
			node = node->left;
		else if (dir > 0)
			node = node->right;
	} while (node);

	return NULL;
}

static int 
ecm_tree_node_height(ecm_tree_node_t *node)
{
	int left_height;
	int right_height;

	if (node) {
		left_height = 0;
		right_height = 0;

		if (node->left)
			left_height = ecm_tree_node_height(node->left);

		if (node->right)
			right_height = ecm_tree_node_height(node->right);

		return ECM_MAX(left_height, right_height) + 1;
	}

	return 0;
}

static ecm_tree_node_t *
ecm_tree_node_rotate_left(ecm_tree_node_t *node)
{
	ecm_tree_node_t *right;
	int a_bal;
	int b_bal;

	right = node->right;

	node->right = right->left;
	right->left = node;

	a_bal = node->balance;
	b_bal = right->balance;

	if (b_bal <= 0) {
		if (a_bal >= 1)
			right->balance = b_bal - 1;
		else
			right->balance = a_bal + b_bal - 2;
		node->balance = a_bal - 1;
	} else {
		if (a_bal <= b_bal)
			right->balance = a_bal - 2;
		else
			right->balance = b_bal - 1;
		node->balance = a_bal - b_bal - 1;
	}

	return right;
}

static ecm_tree_node_t *
ecm_tree_node_rotate_right(ecm_tree_node_t *node)
{
	ecm_tree_node_t *left;
	int a_bal;
	int b_bal;

	left = node->left;

	node->left = left->right;
	left->right = node;

	a_bal = node->balance;
	b_bal = left->balance;

	if (b_bal <= 0) {
		if (b_bal > a_bal)
			left->balance = b_bal + 1;
		else
			left->balance = a_bal + 2;
		node->balance = a_bal - b_bal + 1;
	} else {
		if (a_bal <= -1)
			left->balance = b_bal + 1;
		else
			left->balance = a_bal + b_bal + 2;
		node->balance = a_bal + 1;
	}

	return left;
}

#if 0 /* TODO: It is useless code. Comment out to eliminate warning. */

static void 
ecm_tree_node_check(ecm_tree_node_t *node)
{
	int left_height;
	int right_height;
	int balance;

	if (node) {
		left_height = 0;
		right_height = 0;

		if (node->left)
			left_height = ecm_tree_node_height(node->left);
		if (node->right)
			right_height = ecm_tree_node_height(node->right);

		balance = right_height - left_height;
		if (balance != node->balance)
			//g_log(G_LOG_DOMAIN, G_LOG_LEVEL_INFO,
			//"ecm_tree_node_check: failed: %d ( %d )\n",
			//balance, node->balance); //jj

		if (node->left)
			ecm_tree_node_check(node->left);
		if (node->right)
			ecm_tree_node_check(node->right);
	}
}

#endif
